﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0180_DeleteNode : IAlgorithm
    {
        // 450. 删除二叉搜索树中的节点

        // 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，
        // 并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

        // 一般来说，删除节点可分为两个步骤：
        //  首先找到需要删除的节点；
        //  如果找到了，删除它。

        // 提示:
        //  节点数的范围[0, 10^4].
        //  -10^5 <= Node.val <= 10^5
        //  节点值唯一
        //  root 是合法的二叉搜索树
        //  -10^5 <= key <= 10^5


        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public TreeNode DeleteNode(TreeNode root, int key)
        {
            TreeNode cur = root, curParent = null;
            while (cur != null && cur.val != key)
            {
                curParent = cur;
                if (cur.val > key) cur = cur.left;
                else cur = cur.right;
            }
            if (cur == null) return root;
            if (cur.left == null && cur.right == null) cur = null;
            else if (cur.right == null) cur = cur.left;
            else if (cur.left == null) cur = cur.right;
            else
            {
                TreeNode successor = cur.right, successorParent = cur;
                while (successor.left != null)
                {
                    successorParent = successor;
                    successor = successor.left;
                }
                if (successorParent.val == cur.val) successorParent.right = successor.right;
                else successorParent.left = successor.right;
                successor.right = cur.right;
                successor.left = cur.left;
                cur = successor;
            }
            if (curParent == null) return cur;
            else
            {
                if (curParent.left != null && curParent.left.val == key) curParent.left = cur;
                else curParent.right = cur;
                return root;
            }
        }
    }
}
